Maximal Rectangle
LeetCode 85 | Difficulty: Hard
HardProblem Description
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = [["0"]]
Output: 0
Example 3:
Input: matrix = [["1"]]
Output: 1
Constraints:
- `rows == matrix.length`
- `cols == matrix[i].length`
- `1 <= rows, cols <= 200`
- `matrix[i][j]` is `'0'` or `'1'`.
Topics: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack
Approach
Dynamic Programming
Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.
When to use
Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).
Stack
Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.
When to use
Matching brackets, next greater element, evaluating expressions, backtracking history.
Matrix
Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.
When to use
Grid traversal, island problems, path finding, rotating/transforming matrices.
Solutions
Solution 1: C# (Best: 112 ms)
| Metric | Value |
|---|---|
| Runtime | 112 ms |
| Memory | 43.4 MB |
| Date | 2022-01-26 |
Solution
public class Solution {
public int MaximalRectangle(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
if(n+m == 2) return matrix[0][0] == '1' ? 1 : 0;
int[,] dp = new int[m+1, n+1];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(matrix[i-1][j-1] == '1')
{
dp[i,j] = 1 + dp[i,j-1];
}
}
}
int area = 0;
for (int i =1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(dp[i,j] == 0) continue;
int width = dp[i,j];
int k = i;
int height = 1;
while(k>0 && dp[k,j] > 0)
{
width = Math.Min(width, dp[k--, j]);
area = Math.Max(width * height, area);
height++;
}
}
}
return area;
}
}
📜 5 more C# submission(s)
Submission (2022-01-26) — 116 ms, 42.7 MB
public class Solution {
public int MaximalRectangle(char[][] matrix)
{
int m = matrix.Length;
int n = matrix[0].Length;
if (n + m == 2) return matrix[0][0] == '1' ? 1 : 0;
int area = 0;
int[] dp = new int[n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
dp[j] = (matrix[i][j] == '0') ? 0 : dp[j]+1;
}
// get the max area for this histogram
area = Math.Max(area, GetMaxArea(dp));
}
return area;
}
// code of Largest rectangle in histogram
private int GetMaxArea(int[] heights)
{
Stack<int> s = new Stack<int>();
s.Push(-1);
int len = heights.Length;
int area = 0;
for (int i = 0; i < len; i++)
{
while (s.Peek() != -1 && heights[s.Peek()] > heights[i])
{
int h = heights[s.Pop()];
int width = i - s.Peek() - 1;
area = Math.Max(area, h * width);
}
s.Push(i);
}
while (s.Peek() != -1)
{
int h = heights[s.Pop()];
int width = len - s.Peek() - 1;
area = Math.Max(area, h * width);
}
return area;
}
}
Submission (2022-01-26) — 132 ms, 43.1 MB
public class Solution {
public int MaximalRectangle(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
if(n+m == 2) return matrix[0][0] == '1' ? 1 : 0;
int[,] dp = new int[m+1, n+1];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(matrix[i-1][j-1] == '1')
{
dp[i,j] = 1 + dp[i,j-1];
}
}
}
int area = 0;
for (int i =1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(dp[i,j] == 0) continue;
int width = dp[i,j];
int k = i-1;
int height = 1;
area = Math.Max(area, width * height);
while(k>0 && dp[k,j] > 0 )
{
height++;
width = Math.Min(width, dp[k--, j]);
area = Math.Max(width * height, area);
}
}
}
return area;
}
}
Submission (2022-01-26) — 132 ms, 43.2 MB
public class Solution {
public int MaximalRectangle(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
if(n+m == 2) return matrix[0][0] == '1' ? 1 : 0;
int[,] dp = new int[m+1, n+1];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(matrix[i-1][j-1] == '1')
{
dp[i,j] = 1 + dp[i,j-1];
}
}
}
int area = 0;
for (int i =1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
int width = dp[i,j];
int k = i-1;
int height = 1;
area = Math.Max(area, width * height);
while(k>0 && dp[k,j] > 0 )
{
height++;
width = Math.Min(width, dp[k--, j]);
area = Math.Max(width * height, area);
}
}
}
return area;
}
}
Submission (2022-01-26) — 210 ms, 40.7 MB
public class Solution {
public int MaximalRectangle(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
if(n+m == 2) return matrix[0][0] == '1' ? 1 : 0;
int[,] dp = new int[m+1, n+1];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(matrix[i-1][j-1] == '1')
{
dp[i,j] = 1 + dp[i,j-1];
}
}
}
int area = 0;
for (int i =1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// we cannot form a rectangle as width is zero even though the top rows might have 1
if(dp[i,j] == 0) continue;
int width = dp[i,j];
int k = i;
int height = 1;
while(k>0 && dp[k,j] > 0)
{
width = Math.Min(width, dp[k, j]);
area = Math.Max(width * height, area);
k--;
height++;
}
}
}
return area;
}
}
Submission (2022-01-26) — 211 ms, 39.9 MB
public class Solution {
public int MaximalRectangle(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
if (n + m == 2) return matrix[0][0] == '1' ? 1 : 0;
int area = 0;
int[] dp = new int[n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == '0')
{
dp[j] = 0;
}
else dp[j] += 1;
}
area = Math.Max(area, GetMaxArea(dp));
}
return area;
}
private int GetMaxArea(int[] heights)
{
Stack<int> s = new Stack<int>();
s.Push(-1);
int len = heights.Length;
int area = 0;
for (int i = 0; i < len; i++)
{
while(s.Peek() != -1 && heights[s.Peek()]>heights[i])
{
int h = heights[s.Pop()];
int width = i-s.Peek()-1;
area = Math.Max(area, h * width);
}
s.Push(i);
}
while(s.Peek() != -1)
{
int h = heights[s.Pop()];
int width = len - s.Peek() - 1;
area = Math.Max(area, h * width);
}
return area;
}
}
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| DP (2D) | $O(n × m)$ | $O(n × m)$ |
| Stack | $O(n)$ | $O(n)$ |
Interview Tips
Key Points
- Break the problem into smaller subproblems. Communicate your approach before coding.
- Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
- Consider if you can reduce space by only keeping the last row/few values.
- Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?